package Tree;

import java.util.ArrayList;
import java.util.List;

public class item112 {
}
class Solution112 {
   static   int  sum =0;
    static List<Integer> res = new ArrayList<>();
    public  static boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
         return traverse(root,targetSum-root.val);

//如果碰到叶子节点就把路径上的值进行求和

    }

    private static boolean traverse(TreeNode root, int sum) {
        if(root.left==null&&root.right==null&&sum==0) return true;
        if(root.left==null&&root.right==null) return false;
//        if(root.left!=null)
//        {
//            sum = sum-root.left.val;
            if(traverse(root.left,sum-root.left.val)==true) return true;
//            sum  = sum+root.left.val;
//        }
//        if(root.right!=null)
//        {
//            sum = sum-root.right.val;
            if(traverse(root.right,sum-root.right.val)==true) return true;
//            sum = sum +root.right.val;
//        }
        return false;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2= new TreeNode(2);
        TreeNode node3= new TreeNode(4);
        TreeNode node4= new TreeNode(4);
        TreeNode node5= new TreeNode(5);
        root.left = node1;
        root.right = node2;
        node1.right = node3;
        node1.left = node5;
        node2.right = node4;
     boolean flag= hasPathSum(root,7);
        System.out.println( flag);
    }
}